package com.zhangxiaofanfan.hotcode.third;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 *
 *
 * @author zhangxiaofanfan
 * @date 2024-05-29 08:42:27
 */
public class HotCode035 {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
class LRUCache {
    private final Integer capacity;
    private final Node header;
    private final Node tail;
    private final Map<Integer, Node> mapCache;
    private final Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.header = new Node();
        this.tail = new Node();
        this.header.next = this.tail;
        this.tail.pre = this.header;
        this.map = new HashMap<>();
        this.mapCache = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Integer value = map.get(key);
        updateNode2End(key);
        return value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            updateNode2End(key);
            map.put(key, value);
        } else {
            if (this.map.size() >= this.capacity) {
                Node node = removeNode(this.header.next);
                mapCache.remove(node.value);
                map.remove(node.value);
            }
            map.put(key, value);
            Node newNode = new Node();
            newNode.value = key;
            mapCache.put(key, newNode);
            addNode2End(newNode);
        }
    }

    public void updateNode2End(int key) {
        addNode2End(removeKey(key));
    }

    private Node removeKey(int key) {
        return removeNode(mapCache.get(key));
    }

    private Node removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

    private void addNode2End(Node node) {
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
        node.next = tail;
    }


    static class Node {
        Node pre;
        Node next;
        int value;
    }
}
